import java.util.ArrayDeque;
import java.util.Deque;

public class OrangesRotting {
    private int[] dx = {-1,0,0,1};
    private int[] dy = {0,-1,1,0};
    private int count = 0;
    boolean[][] vis;
    public int orangesRotting(int[][] grid) {
        Deque<int[]> deque = new ArrayDeque<>();
        vis = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    deque.offer(new int[]{i,j});
                    vis[i][j] = true;
                } else if (grid[i][j] == 1) {
                    count++;
                }
            }
        }
        if (deque.size() == 0) {
            if (count != 0) {
                return -1;
            } else {
                return 0;
            }
        }
        int ret = -1;
        while (deque.size() > 0) {
            int size = deque.size();
            ret++;
            for (int i = 0; i < size; i++) {
                int[] tmp = deque.poll();
                for (int j = 0; j < 4; j++) {
                    int x = tmp[0] + dx[j];
                    int y = tmp[1] + dy[j];
                    if (x >= 0 && x < grid.length
                            && y >= 0 && y < grid[0].length
                            && !vis[x][y]
                            && grid[x][y] == 1) {
                        count--;
                        vis[x][y] = true;
                        deque.offer(new int[]{x,y});
                    }
                }
            }
        }
        return count == 0 ? ret : -1;
    }

    public static void main(String[] args) {
        int[][] grid = {{2,1,1},{1,1,0},{0,1,1}};
        System.out.println(new OrangesRotting().orangesRotting(grid));
    }
}
